package sort

import "fmt"

/**
 * 堆
 * @since 2022/8/1 14:19
 * @author 李磊
 */
type Heap struct {
	n    int
	data []int
}

func NewHeap(data []int) *Heap {
	return &Heap{data: data, n: len(data)}
}

func (h *Heap) test() {
	var data = []int{1, 2, 4, 2, 5, 3, 9, 4, 6, 13, 33, 23, 45, 232, 232, 64, 23, 2, 3, 4, 5, 6, 7, 343, 74, 34, 467}
	h.n = len(data)
	h.data = data

	h.create()
	fmt.Println("最小堆")
	for _, v := range data {
		fmt.Println(v)
	}

	fmt.Println("堆排序")
	for h.n > 0 {
		fmt.Println(h.DeleteHead())
	}

}

func (h *Heap) SortUpPrint() {
	for h.n > 0 {
		fmt.Println(h.DeleteHead())
	}
}

func (h *Heap) Sort() {
	for h.n > 0 {
		h.DeleteHead()
	}
}

func (heap *Heap) DeleteHead() int {
	head := heap.data[0]
	heap.data[0], heap.data[heap.n-1] = heap.data[heap.n-1], heap.data[0]
	heap.n--
	heap.ShiftDown(0)
	return head
}

func (h *Heap) create() {
	for i := h.n/2 - 1; i >= 0; i-- {
		h.ShiftDown(i)
	}
}

func (heap *Heap) ShiftDown(i int) {
	flag := false
	for (i+1)*2-1 <= heap.n-1 {
		if flag {
			break
		}
		var t int
		if heap.data[i] > heap.data[(i+1)*2-1] {
			t = (i+1)*2 - 1
		} else {
			t = i
		}
		if (i+1)*2 <= heap.n-1 {
			if heap.data[t] > heap.data[(i+1)*2] {
				t = (i + 1) * 2
			}
		}
		if t != i {
			heap.data[i], heap.data[t] = heap.data[t], heap.data[i]
			i = t
		} else {
			flag = true
		}
	}
}
